#!/usr/bin/python3
# -*- coding:utf-8 -*-
# __author__ == taoyulong2018@gmail.com
# __time__ == 2023/9/4 18:52
#       题目名称： 53. 最大子数组和
#       题目地址： https://leetcode.cn/problems/maximum-subarray/description/
#       题目描述： https://note.youdao.com/s/VjIUrvCD
# ===========================================
from typing import List


class Solution:

    def maxSubArray(self, nums: List[int]) -> int:
        """
            动态规划
            dp[][]      如果元素大于0 累加 小于0 直接存入
            -2, 1, -3, 4, -1, 2, 1, -5, 4
            -2  1  -2   4   3   5   6   1   5
        """
        dp = [0 for _ in range(len(nums))]  # 定义dp
        dp[0] = nums[0]  # 定义第一个元素
        for i in range(1, len(nums)):  # 从第二个元素进行获取
            if dp[i - 1] > 0:  # 如果上一个结果 > 0
                dp[i] = dp[i - 1] + nums[i]
            else:
                dp[i] = nums[i]
        # print(dp)
        res = dp[0]
        for i in range(1, len(nums)):
            res = max(res, dp[i])
        return res

    def maxSubArray3(self, nums: List[int]) -> int:
        max_sum, cur_sum = nums[0], 0  # 定义最大值 和当前sum值
        for index in range(len(nums)):
            num = nums[index]
            if cur_sum > 0:
                cur_sum += num
            else:
                cur_sum = num
            max_sum = max(max_sum, cur_sum)
        return max_sum

    def maxSubArray2(self, nums: List[int]) -> int:
        """
            超出时间限制
        """
        i, j = 0, 1  # 定义两个坐标
        max_value = max(nums)  # 最大值
        while i < j < len(nums):
            max_value = max(max_value, sum(nums[i:j + 1]))
            if j + 1 > len(nums) - 1:
                i += 1
                j = i + 1
            else:
                j += 1
        return max_value


if __name__ == '__main__':
    s = Solution()
    # 6
    print(s.maxSubArray(nums=[-2, 1, -3, 4, -1, 2, 1, -5, 4]))
    # 1
    print(s.maxSubArray(nums=[1]))
    # 23
    print(s.maxSubArray(nums=[5, 4, -1, 7, 8]))
    # 1
    print(s.maxSubArray(nums=[-2, 1]))
